<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 1.3</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 1.3" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 1.3" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-1.xhtml#Chapter-1" rel="prev" title="Chapter 1" />
<link href="Chapter-2.xhtml#Chapter-2" rel="next" title="Chapter 2" />
<link href="1_002e2.xhtml#g_t1_002e2_002e6" rel="prev" title="1.2.6" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t1_002e3"></a>
<nav class="header">
<p>
Next: <a href="Chapter-2.xhtml#Chapter-2" accesskey="n" rel="next">Chapter 2</a>, Prev: <a href="1_002e2.xhtml#g_t1_002e2" accesskey="p" rel="prev">1.2</a>, Up: <a href="Chapter-1.xhtml#Chapter-1" accesskey="u" rel="prev">Chapter 1</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Formulating-Abstractions-with-Higher_002dOrder-Procedures"></a>
<h3 class="section"><span class="secnum">1.3</span><span class="sectitle">Formulating Abstractions with Higher-Order Procedures</span></h3>

<p>We have seen that procedures are, in effect, abstractions that describe
compound operations on numbers independent of the particular numbers.  For
example, when we
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">))</span></pre></div>

<p>we are not talking about the cube of a particular number, but rather about a
method for obtaining the cube of any number.  Of course we could get along
without ever defining this procedure, by always writing expressions such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y y y</span><span class="clo">)</span></pre></div>

<p>and never mentioning <code>cube</code> explicitly.  This would place us at a serious
disadvantage, forcing us to work always at the level of the particular
operations that happen to be primitives in the language (multiplication, in
this case) rather than in terms of higher-level operations.  Our programs would
be able to compute cubes, but our language would lack the ability to express
the concept of cubing.  One of the things we should demand from a powerful
programming language is the ability to build abstractions by assigning names to
common patterns and then to work in terms of the abstractions directly.
Procedures provide this ability.  This is why all but the most primitive
programming languages include mechanisms for defining procedures.
</p>
<p>Yet even in numerical processing we will be severely limited in our ability to
create abstractions if we are restricted to procedures whose parameters must be
numbers.  Often the same programming pattern will be used with a number of
different procedures.  To express such patterns as concepts, we will need to
construct procedures that can accept procedures as arguments or return
procedures as values.  Procedures that manipulate procedures are called
<a id="index-higher_002dorder-procedures"></a>
<em>higher-order procedures</em>.  This section shows how higher-order
procedures can serve as powerful abstraction mechanisms, vastly increasing the
expressive power of our language.
</p>

<a id="g_t1_002e3_002e1"></a>
<a id="Procedures-as-Arguments"></a>
<h4 class="subsection"><span class="secnum">1.3.1</span><span class="sectitle">Procedures as Arguments</span></h4>

<p>Consider the following three procedures.  The first computes the sum of the
integers from <code>a</code> through <code>b</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-integers a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">0</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="opn">(</span><span class="pln">sum-integers </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">))))</span></pre></div>

<p>The second computes the sum of the cubes of the integers in the given range:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-cubes a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">0</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube a</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">sum-cubes </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">))))</span></pre></div>

<p>The third computes the sum of a sequence of terms in the series

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mfrac>
    <mn>1</mn>
    <mrow>
      <mn>1</mn>
      <mo>⋅<!-- ⋅ --></mo>
      <mn>3</mn>
    </mrow>
  </mfrac>
  <mo>+</mo>
  <mfrac>
    <mn>1</mn>
    <mrow>
      <mn>5</mn>
      <mo>⋅<!-- ⋅ --></mo>
      <mn>7</mn>
    </mrow>
  </mfrac>
  <mo>+</mo>
  <mfrac>
    <mn>1</mn>
    <mrow>
      <mn>9</mn>
      <mo>⋅<!-- ⋅ --></mo>
      <mn>11</mn>
    </mrow>
  </mfrac>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>,</mo>
  </mrow>
</math>

which converges to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>π<!-- π --></mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mn>8</mn>
  </mrow>
</math> (very slowly):<a class="footnote_link" id="DOCF49" href="#FOOT49"><sup>49</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-sum a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">1.0</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">2</span><span class="clo">)))</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">pi-sum </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="lit">4</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">))))</span></pre></div>

<p>These three procedures clearly share a common underlying pattern.  They are for
the most part identical, differing only in the name of the procedure, the
function of <code>a</code> used to compute the term to be added, and the function
that provides the next value of <code>a</code>.  We could generate each of the
procedures by filling in slots in the same template:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">name</span></var><span class="pln">⟩ a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">term</span></var><span class="pln">⟩ a</span><span class="clo">)</span><span class="pln"> 
         </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">name</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">next</span></var><span class="pln">⟩ a</span><span class="clo">)</span><span class="pln"> b</span><span class="clo">))))</span></pre></div>

<p>The presence of such a common pattern is strong evidence that there is a useful
abstraction waiting to be brought to the surface.  Indeed, mathematicians long
ago identified the abstraction of <a id="index-summation-of-a-series"></a>
<em>summation of a series</em> and invented
“sigma notation,” for example

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <munderover>
      <mo>∑<!-- ∑ --></mo>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>=</mo>
        <mi>a</mi>
      </mrow>
      <mi>b</mi>
    </munderover>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mo>⋯<!-- ⋯ --></mo>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
</math>

to express this concept.  The power of sigma notation is that it allows
mathematicians to deal with the concept of summation itself rather than only
with particular sums—for example, to formulate general results about sums
that are independent of the particular series being summed.
</p>
<p>Similarly, as program designers, we would like our language to be powerful
enough so that we can write a procedure that expresses the concept of summation
itself rather than only procedures that compute particular sums.  We can do so
readily in our procedural language by taking the common template shown above
and transforming the “slots” into formal parameters:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum term a next b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> a b</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">0</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">term a</span><span class="clo">)</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">sum term </span><span class="opn">(</span><span class="pln">next a</span><span class="clo">)</span><span class="pln"> next b</span><span class="clo">))))</span></pre></div>

<p>Notice that <code>sum</code> takes as its arguments the lower and upper bounds
<code>a</code> and <code>b</code> together with the procedures <code>term</code> and <code>next</code>.
We can use <code>sum</code> just as we would any procedure.  For example, we can use
it (along with a procedure <code>inc</code> that increments its argument by 1) to
define <code>sum-cubes</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">inc n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-cubes a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sum cube a inc b</span><span class="clo">))</span></pre></div>

<p>Using this, we can compute the sum of the cubes of the integers from 1 to 10:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">sum-cubes </span><span class="lit">1</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">3025</span></i>
</pre></div>

<p>With the aid of an identity procedure to compute the term, we can define
<code>sum-integers</code> in terms of <code>sum</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">identity x</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-integers a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sum identity a inc b</span><span class="clo">))</span></pre></div>

<p>Then we can add up the integers from 1 to 10:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">sum-integers </span><span class="lit">1</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">55</span></i>
</pre></div>

<p>We can also define <code>pi-sum</code> in the same way:<a class="footnote_link" id="DOCF50" href="#FOOT50"><sup>50</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-sum a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-term x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">1.0</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">2</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-next x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sum pi-term a pi-next b</span><span class="clo">))</span></pre></div>

<p>Using these procedures, we can compute an approximation to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">8</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-sum </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1000</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">3.139592655589783</span></i>
</pre></div>

<p>Once we have <code>sum</code>, we can use it as a building block in formulating
further concepts.  For instance, the definite integral of a function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>
between the limits <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> can be approximated numerically using the
formula

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <msubsup>
      <mo>∫<!-- ∫ --></mo>
      <mi>a</mi>
      <mi>b</mi>
    </msubsup>
    <mspace width="-0.3em"/>
    <mi>f</mi>
  </mrow>
  <mspace width="thickmathspace"/>
  <mo>=</mo>
  <mspace width="thickmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow>
      <mo>[</mo>
      <mspace width="thickmathspace"/>
      <mi>f</mi>
      <mrow>
        <mo>(</mo>
        <mi>a</mi>
        <mo>+</mo>
        <mfrac>
          <mrow>
            <mi>d</mi>
            <mi>x</mi>
          </mrow>
          <mn>2</mn>
        </mfrac>
        <mo>)</mo>
      </mrow>
    </mrow>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>+</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mrow>
      <mo>(</mo>
      <mi>a</mi>
      <mo>+</mo>
      <mi>d</mi>
      <mi>x</mi>
      <mo>+</mo>
      <mfrac>
        <mrow>
          <mi>d</mi>
          <mi>x</mi>
        </mrow>
        <mn>2</mn>
      </mfrac>
      <mo>)</mo>
    </mrow>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>+</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow>
      <mi>f</mi>
      <mrow>
        <mo>(</mo>
        <mi>a</mi>
        <mo>+</mo>
        <mn>2</mn>
        <mi>d</mi>
        <mi>x</mi>
        <mo>+</mo>
        <mfrac>
          <mrow>
            <mi>d</mi>
            <mi>x</mi>
          </mrow>
          <mn>2</mn>
        </mfrac>
        <mo>)</mo>
      </mrow>
      <mspace width="thinmathspace"/>
      <mo>+</mo>
      <mspace width="thinmathspace"/>
      <mo>…<!-- … --></mo>
      <mspace width="thickmathspace"/>
      <mo>]</mo>
    </mrow>
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math>

for small values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math>.  We can express this directly as a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integral f a b dx</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-dx x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x dx</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum f </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> dx </span><span class="lit">2.0</span><span class="clo">))</span><span class="pln"> add-dx b</span><span class="clo">)</span><span class="pln"> 
     dx</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">integral cube </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0.01</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">.24998750000000042</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">integral cube </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">.249999875000001</span></i>
</pre></div>

<p>(The exact value of the integral of <code>cube</code> between 0 and 1 is 1/4.)
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e29"></a>Exercise 1.29:</strong> Simpson’s Rule is a more accurate
method of numerical integration than the method illustrated above.  Using
Simpson’s Rule, the integral of a function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> between <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> is
approximated as

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mfrac>
    <mi>h</mi>
    <mn>3</mn>
  </mfrac>
  <mo stretchy="false">(</mo>
  <msub>
    <mi>y</mi>
    <mn>0</mn>
  </msub>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <msub>
      <mi>y</mi>
      <mn>2</mn>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <msub>
      <mi>y</mi>
      <mn>3</mn>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <msub>
      <mi>y</mi>
      <mn>4</mn>
    </msub>
  </mrow>
  <mo>+</mo>
  <mo>⋯<!-- ⋯ --></mo>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <msub>
      <mi>y</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>2</mn>
      </mrow>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>4</mn>
    <msub>
      <mi>y</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>+</mo>
    <msub>
      <mi>y</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>h</mi>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo>−<!-- − --></mo>
    <mi>a</mi>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>n</mi>
  </mrow>
</math>, for some even integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>, and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mi>k</mi>
  </msub>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo>+</mo>
    <mi>k</mi>
    <mi>h</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  (Increasing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> increases the
accuracy of the approximation.)  Define a procedure that takes as arguments
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and returns the value of the integral, computed
using Simpson’s Rule.  Use your procedure to integrate <code>cube</code> between 0
and 1 (with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>=</mo>
    <mn>100</mn>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>=</mo>
    <mn>1000</mn>
  </mrow>
</math>), and compare the results to those of
the <code>integral</code> procedure shown above.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e30"></a>Exercise 1.30:</strong> The <code>sum</code> procedure above
generates a linear recursion.  The procedure can be rewritten so that the sum
is performed iteratively.  Show how to do this by filling in the missing
expressions in the following definition:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum term a next b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter a result</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩
        ⟨</span><span class="pun">??</span><span class="pln">⟩
        </span><span class="opn">(</span><span class="pln">iter ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e31"></a>Exercise 1.31:</strong> 
</p>
<ol>
<li> The <code>sum</code> procedure is only the simplest of a vast number of similar
abstractions that can be captured as higher-order procedures.<a class="footnote_link" id="DOCF51" href="#FOOT51"><sup>51</sup></a>  Write an analogous
procedure called <code>product</code> that returns the product of the values of a
function at points over a given range.  Show how to define <code>factorial</code> in
terms of <code>product</code>.  Also use <code>product</code> to compute approximations to
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> using the formula<a class="footnote_link" id="DOCF52" href="#FOOT52"><sup>52</sup></a>

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mfrac>
    <mi>π<!-- π --></mi>
    <mn>4</mn>
  </mfrac>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <mn>2</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>4</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>4</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>6</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>6</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>8</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mo>⋯<!-- ⋯ --></mo>
      </mrow>
      <mrow>
        <mn>3</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>3</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>5</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>5</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>7</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mn>7</mn>
        <mo>⋅<!-- ⋅ --></mo>
        <mo>⋯<!-- ⋯ --></mo>
      </mrow>
    </mfrac>
    <mo>.</mo>
  </mrow>
</math>

</li><li> If your <code>product</code> procedure generates a recursive process, write one that
generates an iterative process.  If it generates an iterative process, write
one that generates a recursive process.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e32"></a>Exercise 1.32:</strong> 
</p>
<ol>
<li> Show that <code>sum</code> and <code>product</code> (<a href="#Exercise-1_002e31">Exercise 1.31</a>) are both special
cases of a still more general notion called <code>accumulate</code> that combines a
collection of terms, using some general accumulation function:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">accumulate 
 combiner null-value term a next b</span><span class="clo">)</span></pre></div>

<p><code>Accumulate</code> takes as arguments the same term and range specifications as
<code>sum</code> and <code>product</code>, together with a <code>combiner</code> procedure (of
two arguments) that specifies how the current term is to be combined with the
accumulation of the preceding terms and a <code>null-value</code> that specifies what
base value to use when the terms run out.  Write <code>accumulate</code> and show how
<code>sum</code> and <code>product</code> can both be defined as simple calls to
<code>accumulate</code>.
</p>
</li><li> If your <code>accumulate</code> procedure generates a recursive process, write one
that generates an iterative process.  If it generates an iterative process,
write one that generates a recursive process.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e33"></a>Exercise 1.33:</strong> You can obtain an even more
general version of <code>accumulate</code> (<a href="#Exercise-1_002e32">Exercise 1.32</a>) by introducing the
notion of a <a id="index-filter"></a>
<em>filter</em> on the terms to be combined.  That is, combine
only those terms derived from values in the range that satisfy a specified
condition.  The resulting <code>filtered-accumulate</code> abstraction takes the same
arguments as accumulate, together with an additional predicate of one argument
that specifies the filter.  Write <code>filtered-accumulate</code> as a procedure.
Show how to express the following using <code>filtered-accumulate</code>:
</p>
<ol>
<li> the sum of the squares of the prime numbers in the interval <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>
(assuming that you have a <code>prime?</code> predicate already written)

</li><li> the product of all the positive integers less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> that are relatively
prime to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> (i.e., all positive integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>&lt;</mo>
    <mi>n</mi>
  </mrow>
</math> such that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>GCD</mtext>
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>n</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>).

</li></ol>
</blockquote>

<a id="g_t1_002e3_002e2"></a>
<a id="Constructing-Procedures-Using-Lambda"></a>
<h4 class="subsection"><span class="secnum">1.3.2</span><span class="sectitle">Constructing Procedures Using <code>Lambda</code></span></h4>

<p>In using <code>sum</code> as in <a href="#g_t1_002e3_002e1">1.3.1</a>, it seems terribly awkward to
have to define trivial procedures such as <code>pi-term</code> and <code>pi-next</code>
just so we can use them as arguments to our higher-order procedure.  Rather
than define <code>pi-next</code> and <code>pi-term</code>, it would be more convenient to
have a way to directly specify “the procedure that returns its input
incremented by 4” and “the procedure that returns the reciprocal of its input
times its input plus 2.”  We can do this by introducing the special form
<code>lambda</code>, which creates procedures.  Using <code>lambda</code> we can describe
what we want as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">4</span><span class="clo">))</span></pre></div>

<p>and
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">1.0</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">2</span><span class="clo">))))</span></pre></div>

<p>Then our <code>pi-sum</code> procedure can be expressed without defining any
auxiliary procedures as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-sum a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sum </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">1.0</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">2</span><span class="clo">))))</span><span class="pln">
       a
       </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">4</span><span class="clo">))</span><span class="pln">
       b</span><span class="clo">))</span></pre></div>

<p>Again using <code>lambda</code>, we can write the <code>integral</code> procedure without
having to define the auxiliary procedure <code>add-dx</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integral f a b dx</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum f </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> dx </span><span class="lit">2.0</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x dx</span><span class="clo">))</span><span class="pln">
            b</span><span class="clo">)</span><span class="pln">
     dx</span><span class="clo">))</span></pre></div>

<p>In general, <code>lambda</code> is used to create procedures in the same way as
<code>define</code>, except that no name is specified for the procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">formal-parameters</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>The resulting procedure is just as much a procedure as one that is created
using <code>define</code>.  The only difference is that it has not been associated
with any name in the environment.  In fact,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">plus4 x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">4</span><span class="clo">))</span></pre></div>

<p>is equivalent to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> plus4 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">4</span><span class="clo">)))</span></pre></div>

<p>We can read a <code>lambda</code> expression as follows:
</p>
<div class="example">
<pre class="example">(lambda                     (x)     (+   x     4))
    |                        |       |   |     |
the procedure of an argument x that adds x and 4
</pre></div>

<p>Like any expression that has a procedure as its value, a <code>lambda</code>
expression can be used as the operator in a combination such as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x y z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x y </span><span class="opn">(</span><span class="pln">square z</span><span class="clo">)))</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">12</span></i>
</pre></div>

<p>or, more generally, in any context where we would normally use a procedure
name.<a class="footnote_link" id="DOCF53" href="#FOOT53"><sup>53</sup></a>
</p>
<a id="Using-let-to-create-local-variables"></a>
<h5 class="subsubheading">Using <code>let</code> to create local variables</h5>

<p>Another use of <code>lambda</code> is in creating local variables.  We often need
local variables in our procedures other than those that have been bound as
formal parameters.  For example, suppose we wish to compute the function

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>+</mo>
    <mi>x</mi>
    <mi>y</mi>
    <msup>
      <mo stretchy="false">)</mo>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>−<!-- − --></mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>+</mo>
    <mi>x</mi>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo>−<!-- − --></mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
</math>

which we could also express as

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <mi>a</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mn>1</mn>
          <mo>+</mo>
          <mi>x</mi>
          <mi>y</mi>
          <mo>,</mo>
        </mrow>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mpadded height="0" depth="0">
            <mphantom>
              <mo stretchy="false">(</mo>
              <mi>x</mi>
              <mo>,</mo>
              <mi>y</mi>
              <mo stretchy="false">)</mo>
            </mphantom>
          </mpadded>
        </mrow>
        <mi>b</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mn>1</mn>
          <mo>−<!-- − --></mo>
          <mi>y</mi>
          <mo>,</mo>
        </mrow>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>f</mi>
          <mo stretchy="false">(</mo>
          <mi>x</mi>
          <mo>,</mo>
          <mi>y</mi>
          <mo stretchy="false">)</mo>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>x</mi>
          <msup>
            <mi>a</mi>
            <mn>2</mn>
          </msup>
        </mrow>
        <mo>+</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>y</mi>
          <mi>b</mi>
        </mrow>
        <mo>+</mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mi>a</mi>
          <mi>b</mi>
          <mo>.</mo>
        </mrow>
      </mtd>
    </mtr>
  </mtable>
</math>

In writing a procedure to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>, we would like to include as local
variables not only <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> but also the names of intermediate
quantities like <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>.  One way to accomplish this is to use an
auxiliary procedure to bind the local variables:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f-helper a b</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">square a</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y b</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">f-helper </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln"> 
            </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">)))</span></pre></div>

<p>Of course, we could use a <code>lambda</code> expression to specify an anonymous
procedure for binding our local variables.  The body of <code>f</code> then becomes a
single call to that procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">a b</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">square a</span><span class="clo">))</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y b</span><span class="clo">)</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b</span><span class="clo">)))</span><span class="pln">
   </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">)))</span></pre></div>

<p>This construct is so useful that there is a special form called <code>let</code> to
make its use more convenient.  Using <code>let</code>, the <code>f</code> procedure could
be written as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">a </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">b </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">square a</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y b</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b</span><span class="clo">))))</span></pre></div>

<p>The general form of a <code>let</code> expression is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₁</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₂</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">₂</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
      </span><span class="roman"><span class="pun">…</span></span><span class="pln">
      </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">ₙ</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">exp</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
  ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>which can be thought of as saying
</p>
<div class="example">
<pre class="example">let ⟨<var>var₁</var>⟩ <span class="roman">have the value</span> ⟨<var>exp₁</var>⟩ <span class="roman">and</span>
    ⟨<var>var₂</var>⟩ <span class="roman">have the value</span> ⟨<var>exp₂</var>⟩ <span class="roman">and</span>
    <span class="roman">…</span>
    ⟨<var>varₙ</var>⟩ <span class="roman">have the value</span> ⟨<var>expₙ</var>⟩
  <span class="roman">in</span> ⟨<var>body</var>⟩
</pre></div>

<p>The first part of the <code>let</code> expression is a list of name-expression pairs.
When the <code>let</code> is evaluated, each name is associated with the value of the
corresponding expression.  The body of the <code>let</code> is evaluated with these
names bound as local variables.  The way this happens is that the <code>let</code>
expression is interpreted as an alternate syntax for
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">var</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">var</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
   ⟨</span><var><span class="pln">body</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
 ⟨</span><var><span class="pln">exp</span><span class="pun">₁</span></var><span class="pln">⟩
 </span><span class="roman"><span class="pun">…</span></span><span class="pln">
 ⟨</span><var><span class="pln">exp</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>No new mechanism is required in the interpreter in order to provide local
variables.  A <code>let</code> expression is simply syntactic sugar for the
underlying <code>lambda</code> application.
</p>
<p>We can see from this equivalence that the scope of a variable specified by a
<code>let</code> expression is the body of the <code>let</code>.  This implies that:
</p>
<ul>
<li> <code>Let</code> allows one to bind variables as locally as possible to where they
are to be used.  For example, if the value of <code>x</code> is 5, the value of the
expression

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="lit">10</span><span class="clo">)))</span><span class="pln">
   x</span><span class="clo">)</span></pre></div>

<p>is 38.  Here, the <code>x</code> in the body of the <code>let</code> is 3, so the value of
the <code>let</code> expression is 33.  On the other hand, the <code>x</code> that is the
second argument to the outermost <code>+</code> is still 5.
</p>
</li><li> The variables’ values are computed outside the <code>let</code>.  This matters when
the expressions that provide the values for the local variables depend upon
variables having the same names as the local variables themselves.  For
example, if the value of <code>x</code> is 2, the expression

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x </span><span class="lit">3</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">y </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x </span><span class="lit">2</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">))</span></pre></div>

<p>will have the value 12 because, inside the body of the <code>let</code>, <code>x</code>
will be 3 and <code>y</code> will be 4 (which is the outer <code>x</code> plus 2).
</p>
</li></ul>

<p>Sometimes we can use internal definitions to get the same effect as with
<code>let</code>.  For example, we could have defined the procedure <code>f</code> above as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f x y</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> a 
    </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x y</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> b </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> y</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">square a</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> y b</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> a b</span><span class="clo">)))</span></pre></div>

<p>We prefer, however, to use <code>let</code> in situations like this and to use
internal <code>define</code> only for internal procedures.<a class="footnote_link" id="DOCF54" href="#FOOT54"><sup>54</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e34"></a>Exercise 1.34:</strong> Suppose we define the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">f g</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g </span><span class="lit">2</span><span class="clo">))</span></pre></div>

<p>Then we have
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">f square</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">4</span></i><span class="pln">

</span><span class="opn">(</span><span class="pln">f </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">z</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> z </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> z </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><i><span class="lit">6</span></i>
</pre></div>

<p>What happens if we (perversely) ask the interpreter to evaluate the combination
<code>(f f)</code>?  Explain.
</p></blockquote>

<a id="g_t1_002e3_002e3"></a>
<a id="Procedures-as-General-Methods"></a>
<h4 class="subsection"><span class="secnum">1.3.3</span><span class="sectitle">Procedures as General Methods</span></h4>

<p>We introduced compound procedures in <a href="1_002e1.xhtml#g_t1_002e1_002e4">1.1.4</a> as a mechanism for
abstracting patterns of numerical operations so as to make them independent of
the particular numbers involved.  With higher-order procedures, such as the
<code>integral</code> procedure of <a href="#g_t1_002e3_002e1">1.3.1</a>, we began to see a more
powerful kind of abstraction: procedures used to express general methods of
computation, independent of the particular functions involved.  In this section
we discuss two more elaborate examples—general methods for finding zeros and
fixed points of functions—and show how these methods can be expressed
directly as procedures.
</p>
<a id="Finding-roots-of-equations-by-the-half_002dinterval-method"></a>
<h5 class="subsubheading">Finding roots of equations by the half-interval method</h5>

<p>The <a id="index-half_002dinterval-method"></a>
<em>half-interval method</em> is a simple but powerful technique for
finding roots of an equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is a continuous
function.  The idea is that, if we are given points <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math> such that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>a</mi>
    <mo stretchy="false">)</mo>
    <mo>&lt;</mo>
    <mn>0</mn>
    <mo>&lt;</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>b</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> must have at least one zero between
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>.  To locate a zero, let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> be the average of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>,
and compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>&gt;</mo>
    <mn>0</mn>
  </mrow>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> must have a zero
between <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>&lt;</mo>
    <mn>0</mn>
  </mrow>
</math>, then <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> must have a zero
between <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>.  Continuing in this way, we can identify smaller and
smaller intervals on which <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> must have a zero.  When we reach a point where
the interval is small enough, the process stops.  Since the interval of
uncertainty is reduced by half at each step of the process, the number of steps
required grows as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi mathvariant="normal">Θ<!-- Θ --></mi>
    <mo stretchy="false">(</mo>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <mi>L</mi>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mspace width="thinmathspace"/>
    <mi>T</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>L</mi>
</math> is the
length of the original interval and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math> is the error tolerance (that is, the
size of the interval we will consider “small enough”).  Here is a procedure
that implements this strategy:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">search f neg-point pos-point</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">midpoint 
         </span><span class="opn">(</span><span class="pln">average neg-point pos-point</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">close-enough? neg-point pos-point</span><span class="clo">)</span><span class="pln">
        midpoint
        </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">test-value </span><span class="opn">(</span><span class="pln">f midpoint</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> 
           </span><span class="opn">((</span><span class="pln">positive? test-value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">search f neg-point midpoint</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">((</span><span class="pln">negative? test-value</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">search f midpoint pos-point</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> midpoint</span><span class="clo">))))))</span></pre></div>

<p>We assume that we are initially given the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> together with points
at which its values are negative and positive.  We first compute the midpoint
of the two given points.  Next we check to see if the given interval is small
enough, and if so we simply return the midpoint as our answer.  Otherwise, we
compute as a test value the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> at the midpoint.  If the test value
is positive, then we continue the process with a new interval running from the
original negative point to the midpoint.  If the test value is negative, we
continue with the interval from the midpoint to the positive point.  Finally,
there is the possibility that the test value is 0, in which case the midpoint
is itself the root we are searching for.
</p>
<p>To test whether the endpoints are “close enough” we can use a procedure
similar to the one used in <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a> for computing square
roots:<a class="footnote_link" id="DOCF55" href="#FOOT55"><sup>55</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">close-enough? x y</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">))</span></pre></div>

<p><code>Search</code> is awkward to use directly, because we can accidentally give it
points at which <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>’s values do not have the required sign, in which case we
get a wrong answer.  Instead we will use <code>search</code> via the following
procedure, which checks to see which of the endpoints has a negative function
value and which has a positive value, and calls the <code>search</code> procedure
accordingly.  If the function has the same sign on the two given points, the
half-interval method cannot be used, in which case the procedure signals an
error.<a class="footnote_link" id="DOCF56" href="#FOOT56"><sup>56</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">half-interval-method f a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">a-value </span><span class="opn">(</span><span class="pln">f a</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">b-value </span><span class="opn">(</span><span class="pln">f b</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">negative? a-value</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">positive? b-value</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">search f a b</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">((</span><span class="kwd">and</span><span class="pln"> </span><span class="opn">(</span><span class="pln">negative? b-value</span><span class="clo">)</span><span class="pln"> 
                </span><span class="opn">(</span><span class="pln">positive? a-value</span><span class="clo">))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">search f b a</span><span class="clo">))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
           </span><span class="opn">(</span><span class="err">error</span><span class="pln"> </span><span class="str">"Values are not of 
                   opposite sign"</span><span class="pln"> a b</span><span class="clo">)))))</span></pre></div>

<p>The following example uses the half-interval method to approximate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> as
the root between 2 and 4 of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">half-interval-method sin </span><span class="lit">2.0</span><span class="pln"> </span><span class="lit">4.0</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">3.14111328125</span></i>
</pre></div>

<p>Here is another example, using the half-interval method to search for a root of
the equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mi>x</mi>
    <mo>−<!-- − --></mo>
    <mn>3</mn>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math> between 1 and 2:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">half-interval-method 
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> x</span><span class="clo">)</span><span class="pln"> </span><span class="lit">3</span><span class="clo">))</span><span class="pln">
 </span><span class="lit">1.0</span><span class="pln">
 </span><span class="lit">2.0</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">1.89306640625</span></i>
</pre></div>

<a id="Finding-fixed-points-of-functions"></a>
<h5 class="subsubheading">Finding fixed points of functions</h5>

<p>A number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is called a <a id="index-fixed-point"></a>
<em>fixed point</em> of a function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>
satisfies the equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mi>x</mi>
  </mrow>
</math>.  For some functions <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> we can
locate a fixed point by beginning with an initial guess and applying <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>
repeatedly,

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
  <mspace width="1em"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
  <mspace width="1em"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo>,</mo>
  </mrow>
  <mspace width="1em"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>,</mo>
  </mrow>
</math>

until the value does not change very much.  Using this idea, we can devise a
procedure <code>fixed-point</code> that takes as inputs a function and an initial
guess and produces an approximation to a fixed point of the function.  We apply
the function repeatedly until we find two successive values whose difference is
less than some prescribed tolerance:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> tolerance </span><span class="lit">0.00001</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fixed-point f first-guess</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">close-enough? v1 v2</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> v1 v2</span><span class="clo">))</span><span class="pln"> 
       tolerance</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">try guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">next </span><span class="opn">(</span><span class="pln">f guess</span><span class="clo">)))</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">close-enough? guess next</span><span class="clo">)</span><span class="pln">
          next
          </span><span class="opn">(</span><span class="pln">try next</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">try first-guess</span><span class="clo">))</span></pre></div>

<p>For example, we can use this method to approximate the fixed point of the
cosine function, starting with 1 as an initial approximation:<a class="footnote_link" id="DOCF57" href="#FOOT57"><sup>57</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">fixed-point cos </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">.7390822985224023</span></i>
</pre></div>

<p>Similarly, we can find a solution to the equation 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mi>sin</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>y</mi>
    <mo>+</mo>
    <mi>cos</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>y</mi>
  </mrow>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">fixed-point </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sin y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cos y</span><span class="clo">)))</span><span class="pln">
             </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">1.2587315962971173</span></i>
</pre></div>

<p>The fixed-point process is reminiscent of the process we used for finding
square roots in <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a>.  Both are based on the idea of repeatedly
improving a guess until the result satisfies some criterion.  In fact, we can
readily formulate the square-root computation as a fixed-point search.
Computing the square root of some number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> requires finding a <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> such
that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>=</mo>
    <mi>x</mi>
  </mrow>
</math>.  Putting this equation into the equivalent form 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>, we recognize that we are looking for a fixed point of the
function<a class="footnote_link" id="DOCF58" href="#FOOT58"><sup>58</sup></a> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>, 
and we can therefore try to compute square roots as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
               </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>Unfortunately, this fixed-point search does not converge.  Consider an initial
guess <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>1</mn>
  </msub>
</math>.  The next guess is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>y</mi>
      <mn>2</mn>
    </msub>
    <mo>=</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
  </mrow>
</math> and the next guess is
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>3</mn>
  </msub>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msub>
      <mi>y</mi>
      <mn>2</mn>
    </msub>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msub>
      <mi>y</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
  <mo>=</mo>
  <msub>
    <mi>y</mi>
    <mn>1</mn>
  </msub>
</math>.  This results in an
infinite loop in which the two guesses <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>1</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>2</mn>
  </msub>
</math> repeat over and
over, oscillating about the answer.
</p>
<p>One way to control such oscillations is to prevent the guesses from changing so
much.  Since the answer is always between our guess <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>, we
can make a new guess that is not as far from <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> as <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math> by averaging
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>, so that the next guess after <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> is 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>2</mn>
      </mfrac>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>+</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> 
instead of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>.  The process of making such a sequence of
guesses is simply the process of looking for a fixed point of 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
  <mo stretchy="false">↦<!-- ↦ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>2</mn>
      </mfrac>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>+</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>: 
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">average y </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x y</span><span class="clo">)))</span><span class="pln">
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>(Note that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>2</mn>
      </mfrac>
    </mrow>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo>+</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is a simple transformation of the
equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
    <mo>;</mo>
  </mrow>
</math> to derive it, add <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> to both sides of the
equation and divide by 2.)
</p>
<p>With this modification, the square-root procedure works.  In fact, if we
unravel the definitions, we can see that the sequence of approximations to the
square root generated here is precisely the same as the one generated by our
original square-root procedure of <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a>.  This approach of
averaging successive approximations to a solution, a technique that we call
<a id="index-average-damping"></a>
<em>average damping</em>, often aids the convergence of fixed-point searches.
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e35"></a>Exercise 1.35:</strong> Show that the golden ratio
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
</math> (<a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a>) is a fixed point of the transformation 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mn>1</mn>
    <mo>+</mo>
    <mn>1</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>x</mi>
  </mrow>
</math>, and use this fact to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
</math> by means 
of the <code>fixed-point</code> procedure.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e36"></a>Exercise 1.36:</strong> Modify <code>fixed-point</code> so that
it prints the sequence of approximations it generates, using the <code>newline</code>
and <code>display</code> primitives shown in <a href="1_002e2.xhtml#Exercise-1_002e22">Exercise 1.22</a>.  Then find a
solution to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mi>x</mi>
    </msup>
    <mo>=</mo>
    <mn>1000</mn>
  </mrow>
</math> by finding a fixed point of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
  <mo stretchy="false">↦<!-- ↦ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <mn>1000</mn>
    <mo stretchy="false">)</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  (Use Scheme’s primitive <code>log</code>
procedure, which computes natural logarithms.)  Compare the number of steps
this takes with and without average damping.  (Note that you cannot start
<code>fixed-point</code> with a guess of 1, as this would cause division by
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>log</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mo stretchy="false">(</mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e37"></a>Exercise 1.37:</strong> 
</p>
<ol>
<li> An infinite <a id="index-continued-fraction"></a>
<em>continued fraction</em> is an expression of the form

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>f</mi>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <msub>
        <mi>N</mi>
        <mn>1</mn>
      </msub>
      <mrow>
        <msub>
          <mi>D</mi>
          <mn>1</mn>
        </msub>
        <mo>+</mo>
        <mfrac>
          <msub>
            <mi>N</mi>
            <mn>2</mn>
          </msub>
          <mrow>
            <msub>
              <mi>D</mi>
              <mn>2</mn>
            </msub>
            <mo>+</mo>
            <mfrac>
              <msub>
                <mi>N</mi>
                <mn>3</mn>
              </msub>
              <mrow>
                <msub>
                  <mi>D</mi>
                  <mn>3</mn>
                </msub>
                <mo>+</mo>
                <mo>…<!-- … --></mo>
              </mrow>
            </mfrac>
          </mrow>
        </mfrac>
      </mrow>
    </mfrac>
    <mo>.</mo>
  </mrow>
</math>

As an example, one can show that the infinite continued fraction expansion with
the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>N</mi>
    <mi>i</mi>
  </msub>
</math> and the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>D</mi>
    <mi>i</mi>
  </msub>
</math> all equal to 1 produces <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>φ<!-- φ --></mi>
  </mrow>
</math>, where
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>φ<!-- φ --></mi>
</math> is the golden ratio (described in <a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a>).  One way to
approximate an infinite continued fraction is to truncate the expansion after a
given number of terms.  Such a truncation—a so-called <a id="index-k_002dterm"></a>
finite continued fraction
<em><i>k</i>-term
finite continued fraction</em>—has the form

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <msub>
        <mi>N</mi>
        <mn>1</mn>
      </msub>
      <mrow>
        <msub>
          <mi>D</mi>
          <mn>1</mn>
        </msub>
        <mo>+</mo>
        <mfrac>
          <msub>
            <mi>N</mi>
            <mn>2</mn>
          </msub>
          <mrow>
            <mo>⋱<!-- ⋱ --></mo>
            <mo>+</mo>
            <mfrac>
              <msub>
                <mi>N</mi>
                <mi>k</mi>
              </msub>
              <msub>
                <mi>D</mi>
                <mi>k</mi>
              </msub>
            </mfrac>
          </mrow>
        </mfrac>
      </mrow>
    </mfrac>
    <mo>.</mo>
  </mrow>
</math>

Suppose that <code>n</code> and <code>d</code> are procedures of one argument (the term
index <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math>) that return the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>N</mi>
    <mi>i</mi>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>D</mi>
    <mi>i</mi>
  </msub>
</math> of the terms of the
continued fraction.  Define a procedure <code>cont-frac</code> such that evaluating
<code>(cont-frac n d k)</code> computes the value of the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>k</mi>
</math>-term finite continued
fraction.  Check your procedure by approximating <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>φ<!-- φ --></mi>
  </mrow>
</math> using

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cont-frac </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">i</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">i</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1.0</span><span class="clo">)</span><span class="pln">
           k</span><span class="clo">)</span></pre></div>

<p>for successive values of <code>k</code>.  How large must you make <code>k</code> in order
to get an approximation that is accurate to 4 decimal places?
</p>
</li><li> If your <code>cont-frac</code> procedure generates a recursive process, write one
that generates an iterative process.  If it generates an iterative process,
write one that generates a recursive process.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e38"></a>Exercise 1.38:</strong> In 1737, the Swiss mathematician
Leonhard Euler published a memoir <cite>De Fractionibus Continuis</cite>, which
included a continued fraction expansion for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>e</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
  </mrow>
</math>, where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>e</mi>
</math> is the base
of the natural logarithms.  In this fraction, the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>N</mi>
    <mi>i</mi>
  </msub>
</math> are all 1, and
the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>D</mi>
    <mi>i</mi>
  </msub>
</math> are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ….
Write a program that uses your <code>cont-frac</code> procedure from <a href="#Exercise-1_002e37">Exercise 1.37</a> 
to approximate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>e</mi>
</math>, based on Euler’s expansion.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e39"></a>Exercise 1.39:</strong> A continued fraction
representation of the tangent function was published in 1770 by the German
mathematician J.H. Lambert:

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>tan</mi>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>x</mi>
      <mrow>
        <mn>1</mn>
        <mo>−<!-- − --></mo>
        <mfrac>
          <msup>
            <mi>x</mi>
            <mn>2</mn>
          </msup>
          <mrow>
            <mn>3</mn>
            <mo>−<!-- − --></mo>
            <mfrac>
              <msup>
                <mi>x</mi>
                <mn>2</mn>
              </msup>
              <mrow>
                <mn>5</mn>
                <mo>−<!-- − --></mo>
                <mo>…<!-- … --></mo>
              </mrow>
            </mfrac>
          </mrow>
        </mfrac>
      </mrow>
    </mfrac>
    <mspace width="thinmathspace"/>
    <mo>,</mo>
  </mrow>
</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is in radians.  Define a procedure <code>(tan-cf x k)</code> that
computes an approximation to the tangent function based on Lambert’s formula.
<code>k</code> specifies the number of terms to compute, as in <a href="#Exercise-1_002e37">Exercise 1.37</a>.
</p></blockquote>

<a id="g_t1_002e3_002e4"></a>
<a id="Procedures-as-Returned-Values"></a>
<h4 class="subsection"><span class="secnum">1.3.4</span><span class="sectitle">Procedures as Returned Values</span></h4>

<p>The above examples demonstrate how the ability to pass procedures as arguments
significantly enhances the expressive power of our programming language.  We
can achieve even more expressive power by creating procedures whose returned
values are themselves procedures.
</p>
<p>We can illustrate this idea by looking again at the fixed-point example
described at the end of <a href="#g_t1_002e3_002e3">1.3.3</a>.  We formulated a new version of
the square-root procedure as a fixed-point search, starting with the
observation that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>x</mi>
  </msqrt>
</math> is a fixed-point of the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>.  Then we used average damping to make the approximations converge.
Average damping is a useful general technique in itself.  Namely, given a
function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>, we consider the function whose value at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is equal to the
average of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
</p>
<p>We can express the idea of average damping by means of the following procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">average-damp f</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
    </span><span class="opn">(</span><span class="pln">average x </span><span class="opn">(</span><span class="pln">f x</span><span class="clo">))))</span></pre></div>

<p><code>Average-damp</code> is a procedure that takes as its argument a procedure
<code>f</code> and returns as its value a procedure (produced by the <code>lambda</code>)
that, when applied to a number <code>x</code>, produces the average of <code>x</code> and
<code>(f x)</code>.  For example, applying <code>average-damp</code> to the <code>square</code>
procedure produces a procedure whose value at some number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is the average
of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>x</mi>
    <mn>2</mn>
  </msup>
</math>.  Applying this resulting procedure to 10 returns the
average of 10 and 100, or 55:<a class="footnote_link" id="DOCF59" href="#FOOT59"><sup>59</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">average-damp square</span><span class="clo">)</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">55</span></i>
</pre></div>

<p>Using <code>average-damp</code>, we can reformulate the square-root procedure as
follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point 
   </span><span class="opn">(</span><span class="pln">average-damp 
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x y</span><span class="clo">)))</span><span class="pln">
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>Notice how this formulation makes explicit the three ideas in the method:
fixed-point search, average damping, and the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>.
It is instructive to compare this formulation of the square-root method with
the original version given in <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a>.  Bear in mind that these
procedures express the same process, and notice how much clearer the idea
becomes when we express the process in terms of these abstractions.  In
general, there are many ways to formulate a process as a procedure.
Experienced programmers know how to choose procedural formulations that are
particularly perspicuous, and where useful elements of the process are exposed
as separate entities that can be reused in other applications.  As a simple
example of reuse, notice that the cube root of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is a fixed point of the
function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>, so we can immediately generalize our
square-root procedure to one that extracts cube roots:<a class="footnote_link" id="DOCF60" href="#FOOT60"><sup>60</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube-root x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point 
   </span><span class="opn">(</span><span class="pln">average-damp 
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">square y</span><span class="clo">))))</span><span class="pln">
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<a id="Newton_0027s-method"></a>
<h5 class="subsubheading">Newton’s method</h5>

<p>When we first introduced the square-root procedure, in <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a>, we
mentioned that this was a special case of <a id="index-Newton_0027s-method"></a>
<em>Newton’s method</em>.  
If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is a differentiable function, then a solution of the equation
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math> is a fixed point of the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> where

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mi>x</mi>
  <mo>−<!-- − --></mo>
  <mfrac>
    <mrow>
      <mi>g</mi>
      <mo stretchy="false">(</mo>
      <mi>x</mi>
      <mo stretchy="false">)</mo>
    </mrow>
    <mrow>
      <mi>D</mi>
      <mi>g</mi>
      <mo stretchy="false">(</mo>
      <mi>x</mi>
      <mo stretchy="false">)</mo>
    </mrow>
  </mfrac>
</math>

and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>D</mi>
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is the derivative of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> evaluated at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>.  Newton’s
method is the use of the fixed-point method we saw above to approximate a
solution of the equation by finding a fixed point of the function
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
  </mrow>
</math>.<a class="footnote_link" id="DOCF61" href="#FOOT61"><sup>61</sup></a>
</p>
<p>For many functions <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> and for sufficiently good initial guesses for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>,
Newton’s method converges very rapidly to a solution of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>0</mn>
  </mrow>
</math>.<a class="footnote_link" id="DOCF62" href="#FOOT62"><sup>62</sup></a>
</p>
<p>In order to implement Newton’s method as a procedure, we must first express the
idea of derivative.  Note that “derivative,” like average damping, is
something that transforms a function into another function.  For instance, the
derivative of the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
  </mrow>
</math> is the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mn>3</mn>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.
In general, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> is a function and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math> is a small number,
then the derivative <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>D</mi>
    <mi>g</mi>
  </mrow>
</math> of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> is the function whose value at any
number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is given (in the limit of small <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math>) by

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>D</mi>
  <mi>g</mi>
  <mo stretchy="false">(</mo>
  <mi>x</mi>
  <mo stretchy="false">)</mo>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mrow>
        <mi>g</mi>
        <mo stretchy="false">(</mo>
        <mi>x</mi>
        <mo>+</mo>
        <mi>d</mi>
        <mi>x</mi>
        <mo stretchy="false">)</mo>
        <mo>−<!-- − --></mo>
        <mi>g</mi>
        <mo stretchy="false">(</mo>
        <mi>x</mi>
        <mo stretchy="false">)</mo>
      </mrow>
      <mrow>
        <mi>d</mi>
        <mi>x</mi>
      </mrow>
    </mfrac>
    <mo>.</mo>
  </mrow>
</math>

Thus, we can express the idea of derivative (taking <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math> to be, say,
0.00001) as the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">deriv g</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x dx</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g x</span><span class="clo">))</span><span class="pln">
       dx</span><span class="clo">)))</span></pre></div>

<p>along with the definition
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> dx </span><span class="lit">0.00001</span><span class="clo">)</span></pre></div>

<p>Like <code>average-damp</code>, <code>deriv</code> is a procedure that takes a procedure as
argument and returns a procedure as value.  For example, to approximate the
derivative of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
  </mrow>
</math> at 5 (whose exact value is 75) we can evaluate
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cube x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x x x</span><span class="clo">))</span><span class="pln">

</span><span class="opn">((</span><span class="pln">deriv cube</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">75.00014999664018</span></i>
</pre></div>

<p>With the aid of <code>deriv</code>, we can express Newton’s method as a fixed-point
process:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newton-transform g</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> x </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">g x</span><span class="clo">)</span><span class="pln"> 
            </span><span class="opn">((</span><span class="pln">deriv g</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">newtons-method g guess</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point </span><span class="opn">(</span><span class="pln">newton-transform g</span><span class="clo">)</span><span class="pln"> 
               guess</span><span class="clo">))</span></pre></div>

<p>The <code>newton-transform</code> procedure expresses the formula at the beginning of
this section, and <code>newtons-method</code> is readily defined in terms of this.
It takes as arguments a procedure that computes the function for which we want
to find a zero, together with an initial guess.  For instance, to find the
square root of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>, we can use Newton’s method to find a zero of the function
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>−<!-- − --></mo>
    <mi>x</mi>
  </mrow>
</math> starting with an initial guess of 1.<a class="footnote_link" id="DOCF63" href="#FOOT63"><sup>63</sup></a>
</p>
<p>This provides yet another form of the square-root procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newtons-method 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square y</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> 
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<a id="Abstractions-and-first_002dclass-procedures"></a>
<h5 class="subsubheading">Abstractions and first-class procedures</h5>

<p>We’ve seen two ways to express the square-root computation as an instance of a
more general method, once as a fixed-point search and once using Newton’s
method.  Since Newton’s method was itself expressed as a fixed-point process,
we actually saw two ways to compute square roots as fixed points.  Each method
begins with a function and finds a fixed point of some transformation of the
function.  We can express this general idea itself as a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fixed-point-of-transform 
         g transform guess</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point </span><span class="opn">(</span><span class="pln">transform g</span><span class="clo">)</span><span class="pln"> guess</span><span class="clo">))</span></pre></div>

<p>This very general procedure takes as its arguments a procedure <code>g</code> that
computes some function, a procedure that transforms <code>g</code>, and an initial
guess.  The returned result is a fixed point of the transformed function.
</p>
<p>Using this abstraction, we can recast the first square-root computation from
this section (where we look for a fixed point of the average-damped version of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>) as an instance of this general method:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point-of-transform 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x y</span><span class="clo">))</span><span class="pln">
   average-damp
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>Similarly, we can express the second square-root computation from this section
(an instance of Newton’s method that finds a fixed point of the Newton
transform of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
    <mo>−<!-- − --></mo>
    <mi>x</mi>
  </mrow>
</math>) as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">fixed-point-of-transform 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square y</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
   newton-transform
   </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>We began section <a href="#g_t1_002e3">1.3</a> with the observation that compound procedures are a
crucial abstraction mechanism, because they permit us to express general
methods of computing as explicit elements in our programming language.  Now
we’ve seen how higher-order procedures permit us to manipulate these general
methods to create further abstractions.
</p>
<p>As programmers, we should be alert to opportunities to identify the underlying
abstractions in our programs and to build upon them and generalize them to
create more powerful abstractions.  This is not to say that one should always
write programs in the most abstract way possible; expert programmers know how
to choose the level of abstraction appropriate to their task.  But it is
important to be able to think in terms of these abstractions, so that we can be
ready to apply them in new contexts.  The significance of higher-order
procedures is that they enable us to represent these abstractions explicitly as
elements in our programming language, so that they can be handled just like
other computational elements.
</p>
<p>In general, programming languages impose restrictions on the ways in which
computational elements can be manipulated.  Elements with the fewest
restrictions are said to have <a id="index-first_002dclass"></a>
<em>first-class</em> status.  Some of the
“rights and privileges” of first-class elements are:<a class="footnote_link" id="DOCF64" href="#FOOT64"><sup>64</sup></a>
</p>
<ul>
<li> They may be named by variables.

</li><li> They may be passed as arguments to procedures.

</li><li> They may be returned as the results of procedures.

</li><li> They may be included in data structures.<a class="footnote_link" id="DOCF65" href="#FOOT65"><sup>65</sup></a>

</li></ul>

<p>Lisp, unlike other common programming languages, awards procedures full
first-class status.  This poses challenges for efficient implementation, but
the resulting gain in expressive power is enormous.<a class="footnote_link" id="DOCF66" href="#FOOT66"><sup>66</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-1_002e40"></a>Exercise 1.40:</strong> Define a procedure <code>cubic</code>
that can be used together with the <code>newtons-method</code> procedure in
expressions of the form
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">newtons-method </span><span class="opn">(</span><span class="pln">cubic a b c</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">)</span></pre></div>

<p>to approximate zeros of the cubic <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <mi>a</mi>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <mi>b</mi>
    <mi>x</mi>
    <mo>+</mo>
    <mi>c</mi>
  </mrow>
</math>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e41"></a>Exercise 1.41:</strong> Define a procedure <code>double</code>
that takes a procedure of one argument as argument and returns a procedure that
applies the original procedure twice.  For example, if <code>inc</code> is a
procedure that adds 1 to its argument, then <code>(double inc)</code> should be a
procedure that adds 2.  What value is returned by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(((</span><span class="pln">double </span><span class="opn">(</span><span class="pln">double double</span><span class="clo">))</span><span class="pln"> inc</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e42"></a>Exercise 1.42:</strong> Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> be two
one-argument functions.  The <a id="index-composition"></a>
<em>composition</em> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> after <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>g</mi>
</math> is defined
to be the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  Define a procedure
<code>compose</code> that implements composition.  For example, if <code>inc</code> is a
procedure that adds 1 to its argument,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">compose square inc</span><span class="clo">)</span><span class="pln"> </span><span class="lit">6</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">49</span></i>
</pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e43"></a>Exercise 1.43:</strong> If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is a numerical function
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is a positive integer, then we can form the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> repeated
application of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>, which is defined to be the function whose value at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>
is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mo>…<!-- … --></mo>
    <mo stretchy="false">(</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
    <mo>…<!-- … --></mo>
    <mo stretchy="false">)</mo>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  For example, if <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is the
function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math>, then the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> repeated application of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is
the function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mo>+</mo>
    <mi>n</mi>
  </mrow>
</math>.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is the operation of squaring a
number, then the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> repeated application of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is the function that
raises its argument to the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mn>2</mn>
      <mi>n</mi>
    </msup>
    <mtext>-th</mtext>
  </mrow>
</math> power.  Write a procedure that takes as
inputs a procedure that computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> and a positive integer <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> and returns
the procedure that computes the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> repeated application of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>.  Your
procedure should be able to be used as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">((</span><span class="pln">repeated square </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">625</span></i>
</pre></div>

<p>Hint: You may find it convenient to use <code>compose</code> from <a href="#Exercise-1_002e42">Exercise 1.42</a>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e44"></a>Exercise 1.44:</strong> The idea of <a id="index-smoothing"></a>
<em>smoothing</em> a
function is an important concept in signal processing.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is a function
and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>x</mi>
  </mrow>
</math> is some small number, then the smoothed version of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is the
function whose value at a point <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> is the average of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>−<!-- − --></mo>
    <mi>d</mi>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>x</mi>
    <mo>+</mo>
    <mi>d</mi>
    <mi>x</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  Write a procedure
<code>smooth</code> that takes as input a procedure that computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> and returns a
procedure that computes the smoothed <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math>.  It is sometimes valuable to
repeatedly smooth a function (that is, smooth the smoothed function, and so on)
to obtain the <a id="index-n_002dfold-smoothed-function"></a>
<em><i>n</i>-fold smoothed function</em>.  Show how to generate
the <i>n</i>-fold smoothed function of any given function using <code>smooth</code> and
<code>repeated</code> from <a href="#Exercise-1_002e43">Exercise 1.43</a>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e45"></a>Exercise 1.45:</strong> We saw in <a href="#g_t1_002e3_002e3">1.3.3</a>
that attempting to compute square roots by naively finding a fixed point of
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math> does not converge, and that this can be fixed by average
damping.  The same method works for finding cube roots as fixed points of the
average-damped <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>y</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.  Unfortunately, the process does not
work for fourth roots—a single average damp is not enough to make a
fixed-point search for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>y</mi>
      <mn>3</mn>
    </msup>
  </mrow>
</math> converge.  On the other hand, if
we average damp twice (i.e., use the average damp of the average damp of 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>y</mi>
      <mn>3</mn>
    </msup>
  </mrow>
</math>) the fixed-point search does converge.  Do some experiments
to determine how many average damps are required to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> roots as a
fixed-point search based upon repeated average damping of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <msup>
      <mi>y</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mspace width="0.1em"/>
        <mi>n</mi>
        <mo>−<!-- − --></mo>
        <mn>1</mn>
      </mrow>
    </msup>
  </mrow>
</math>.  
Use this to implement a simple procedure for computing
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> roots using <code>fixed-point</code>, <code>average-damp</code>, and the
<code>repeated</code> procedure of <a href="#Exercise-1_002e43">Exercise 1.43</a>.  Assume that any arithmetic
operations you need are available as primitives.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-1_002e46"></a>Exercise 1.46:</strong> Several of the numerical methods
described in this chapter are instances of an extremely general computational
strategy known as <a id="index-iterative-improvement"></a>
<em>iterative improvement</em>.  Iterative improvement says
that, to compute something, we start with an initial guess for the answer, test
if the guess is good enough, and otherwise improve the guess and continue the
process using the improved guess as the new guess.  Write a procedure
<code>iterative-improve</code> that takes two procedures as arguments: a method for
telling whether a guess is good enough and a method for improving a guess.
<code>Iterative-improve</code> should return as its value a procedure that takes a
guess as argument and keeps improving the guess until it is good enough.
Rewrite the <code>sqrt</code> procedure of <a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a> and the
<code>fixed-point</code> procedure of <a href="#g_t1_002e3_002e3">1.3.3</a> in terms of
<code>iterative-improve</code>.
</p></blockquote>

<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT49"><p><a class="footnote_backlink" href="#DOCF49"><sup>49</sup></a>
This series, usually
written in the equivalent form 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>π<!-- π --></mi>
      <mn>4</mn>
    </mfrac>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mo>−<!-- − --></mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>3</mn>
      </mfrac>
    </mrow>
    <mo>+</mo>
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>5</mn>
      </mfrac>
    </mrow>
  </mrow>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>7</mn>
      </mfrac>
    </mrow>
    <mo>+</mo>
    <mo>…<!-- … --></mo>
  </mrow>
</math>, 
is due to Leibniz.  We’ll see how to use this as the basis for some
fancy numerical tricks in <a href="3_002e5.xhtml#g_t3_002e5_002e3">3.5.3</a>.</p>
</div>
<div id="FOOT50"><p><a class="footnote_backlink" href="#DOCF50"><sup>50</sup></a>
Notice that we have
used block structure (<a href="1_002e1.xhtml#g_t1_002e1_002e8">1.1.8</a>) to embed the definitions of
<code>pi-next</code> and <code>pi-term</code> within <code>pi-sum</code>, since these procedures
are unlikely to be useful for any other purpose.  We will see how to get rid of
them altogether in <a href="#g_t1_002e3_002e2">1.3.2</a>.</p>
</div>
<div id="FOOT51"><p><a class="footnote_backlink" href="#DOCF51"><sup>51</sup></a>
The
intent of <a href="#Exercise-1_002e31">Exercise 1.31</a> through <a href="#Exercise-1_002e33">Exercise 1.33</a> is to demonstrate the
expressive power that is attained by using an appropriate abstraction to
consolidate many seemingly disparate operations.  However, though accumulation
and filtering are elegant ideas, our hands are somewhat tied in using them at
this point since we do not yet have data structures to provide suitable means
of combination for these abstractions.  We will return to these ideas in
<a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a> when we show how to use <a id="index-sequences"></a>
<em>sequences</em> as interfaces
for combining filters and accumulators to build even more powerful
abstractions.  We will see there how these methods really come into their own
as a powerful and elegant approach to designing programs.</p>
</div>
<div id="FOOT52"><p><a class="footnote_backlink" href="#DOCF52"><sup>52</sup></a>
This formula was discovered by the
seventeenth-century English mathematician John Wallis.</p>
</div>
<div id="FOOT53"><p><a class="footnote_backlink" href="#DOCF53"><sup>53</sup></a>
It would be clearer and less intimidating to people learning
Lisp if a name more obvious than <code>lambda</code>, such as <code>make-procedure</code>,
were used.  But the convention is firmly entrenched.  The notation is adopted
from the λ-calculus, a mathematical formalism introduced by the
mathematical logician Alonzo <a href="References.xhtml#Church-_00281941_0029">Church (1941)</a>.  Church developed the 
λ-calculus to provide a rigorous foundation for studying the 
notions of function
and function application.  The λ-calculus has become a basic tool
for mathematical investigations of the semantics of programming languages.</p>
</div>
<div id="FOOT54"><p><a class="footnote_backlink" href="#DOCF54"><sup>54</sup></a>
Understanding
internal definitions well enough to be sure a program means what we intend it
to mean requires a more elaborate model of the evaluation process than we have
presented in this chapter.  The subtleties do not arise with internal
definitions of procedures, however.  We will return to this issue in 
<a href="4_002e1.xhtml#g_t4_002e1_002e6">4.1.6</a>, after we learn more about evaluation.</p>
</div>
<div id="FOOT55"><p><a class="footnote_backlink" href="#DOCF55"><sup>55</sup></a>
We have used 0.001 as a representative “small” number to
indicate a tolerance for the acceptable error in a calculation.  The
appropriate tolerance for a real calculation depends upon the problem to be
solved and the limitations of the computer and the algorithm.  This is often a
very subtle consideration, requiring help from a numerical analyst or some
other kind of magician.</p>
</div>
<div id="FOOT56"><p><a class="footnote_backlink" href="#DOCF56"><sup>56</sup></a>
This can be accomplished using <code>error</code>, which takes as
arguments a number of items that are printed as error messages.</p>
</div>
<div id="FOOT57"><p><a class="footnote_backlink" href="#DOCF57"><sup>57</sup></a>
Try this
during a boring lecture: Set your calculator to radians mode and then
repeatedly press the <code>cos</code> button until you obtain the fixed point.</p>
</div>
<div id="FOOT58"><p><a class="footnote_backlink" href="#DOCF58"><sup>58</sup></a>
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↦<!-- ↦ --></mo>
</math> (pronounced “maps to”) is the mathematician’s way of
writing <code>lambda</code>.  <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math> means <code>(lambda (y) (/ x y))</code>,
that is, the function whose value at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>y</mi>
  </mrow>
</math>.</p>
</div>
<div id="FOOT59"><p><a class="footnote_backlink" href="#DOCF59"><sup>59</sup></a>
Observe that this is a combination whose
operator is itself a combination.  <a href="1_002e1.xhtml#Exercise-1_002e4">Exercise 1.4</a> already demonstrated the
ability to form such combinations, but that was only a toy example.  Here we
begin to see the real need for such combinations—when applying a procedure
that is obtained as the value returned by a higher-order procedure.</p>
</div>
<div id="FOOT60"><p><a class="footnote_backlink" href="#DOCF60"><sup>60</sup></a>
See
<a href="#Exercise-1_002e45">Exercise 1.45</a> for a further generalization.</p>
</div>
<div id="FOOT61"><p><a class="footnote_backlink" href="#DOCF61"><sup>61</sup></a>
Elementary calculus books usually describe Newton’s method in
terms of the sequence of approximations <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>x</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>=</mo>
  <msub>
    <mi>x</mi>
    <mi>n</mi>
  </msub>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>x</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">)</mo>
    <mspace width="thinmathspace"/>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>D</mi>
    <mi>g</mi>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>x</mi>
      <mi>n</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>. 
Having language for talking about processes and using the idea of fixed points 
simplifies the description of the method.</p>
</div>
<div id="FOOT62"><p><a class="footnote_backlink" href="#DOCF62"><sup>62</sup></a>
Newton’s
method does not always converge to an answer, but it can
be shown that in favorable cases each iteration doubles the number-of-digits
accuracy of the approximation to the solution.  In such cases, Newton’s method
will converge much more rapidly than the half-interval method.</p>
</div>
<div id="FOOT63"><p><a class="footnote_backlink" href="#DOCF63"><sup>63</sup></a>
For
finding square roots, Newton’s method converges rapidly to the correct solution
from any starting point.</p>
</div>
<div id="FOOT64"><p><a class="footnote_backlink" href="#DOCF64"><sup>64</sup></a>
The notion of
first-class status of programming-language elements is due to the British
computer scientist Christopher Strachey (1916-1975).</p>
</div>
<div id="FOOT65"><p><a class="footnote_backlink" href="#DOCF65"><sup>65</sup></a>
We’ll see examples of this
after we introduce data structures in <a href="Chapter-2.xhtml#Chapter-2">Chapter 2<!-- /@w --></a>.</p>
</div>
<div id="FOOT66"><p><a class="footnote_backlink" href="#DOCF66"><sup>66</sup></a>
The major
implementation cost of first-class procedures is that allowing procedures to be
returned as values requires reserving storage for a procedure’s free variables
even while the procedure is not executing.  In the Scheme implementation we
will study in <a href="4_002e1.xhtml#g_t4_002e1">4.1</a>, these variables are stored in the procedure’s
environment.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="Chapter-2.xhtml#Chapter-2" accesskey="n" rel="next">Chapter 2</a>, Prev: <a href="1_002e2.xhtml#g_t1_002e2" accesskey="p" rel="prev">1.2</a>, Up: <a href="#g_t1_002e3" accesskey="u" rel="prev">1.3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>